package LRU 

import "container/list"

// LRU缓存
type LRUCache struct {
	cache map[int]string //存储业务数据
	lst list.List  // 辅助的链表，用于决定淘汰谁
	cap int // 缓存容量
}

func NewLRUCache(cap int) *LRUCache {
	return &LRUCache{
		cache: make(map[int]string),
		lst: list.List{},
		cap: cap,
	}
}

//向缓存中添加数据添加前先判断是否已经存在map（）,时间复杂度为O(1)
func (lru *LRUCache) Add(key int, value string) {
	if len(lru.cache) >= lru.cap{
		back := lru.lst.Back()
		delete(lru.cache, back.Value.(int))
		lru.lst.Remove(back)
	}
	// 添加数据,放到首部
	lru.cache[key] = value
	lru.lst.PushFront(key)
}

// 从辅助数组中找到一个元素，时间复杂度为O(N)
func (lru *LRUCache) find(key int) *list.Element{
	if lru.lst.Len() == 0 {
		return nil
	}
	head := lru.lst.Front() // 链表头
	for {
		if head == nil{
			break;
		}
		if head.Value.(int) == key { //head.Value.(int) 这段代码的作用是从 head.Value 中断言并提取出一个 int 类型的值。
			return head
		}else{
			head = head.Next()
		}

	}
	return nil
}

// 从缓存中寻找数据，时间复杂度为O(N)
func (lru *LRUCache) Get(key int) (string, bool) {
	value,exist := lru.cache[key]
	ele := lru.find(key)
	if ele != nil {
		lru.lst.MoveToFront(ele)
	}
	return value, exist
}